package com.fjl.list.leetcode82;

import com.fjl.list.ListNode;

/**
 * @Description
 * @Author: 01195
 * @Date: 2025/2/18 9:54
 */
public class DeleteDuplicatesNode {
    public static void main(String[] args) {

    }

    // 给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。
    public ListNode deleteDuplicates1(ListNode head) {
        // 将原链表分解为两条链表
        // 一条链表存放不重复的节点，另一条链表存放重复的节点
        // 运用虚拟头结点技巧，题目说了 node.val <= 100，所以用 101 作为虚拟头结点
        ListNode dummyUniq = new ListNode(101);
        ListNode dummyDup = new ListNode(101);
        ListNode pUniq = dummyUniq, pDup = dummyDup;
        ListNode p = head;
        while (p != null) {
            // 判断是否是重复节点
            if ((p.next != null && p.next.val == p.val) || p.val == pDup.val) {
                // 重复节点接到重复链表后面
                pDup.next = p;
                pDup = pDup.next;
            } else {
                pUniq.next = p;
                pUniq = pUniq.next;
            }

            // 将原链表和新链表断开
            ListNode temp = p.next;
            p.next = null;
            p = temp;
        }

        return dummyUniq.next;
    }

    // 快慢双指针解法
    public ListNode deleteDuplicates2(ListNode head) {
        ListNode dummy = new ListNode(101);
        ListNode p = dummy, q = head;
        while (q != null) {
            if (q.next != null && q.next.val == q.val) {
                while (q.next != null && q.val == q.next.val) {
                    q = q.next;
                }
                q = q.next;
                // 不过下一段元素也可能重复，等下一轮 while 循环判断
            } else {
                p.next = q;
                p = p.next;
                // 将原链表和新链表断开
                ListNode temp = q.next;
                q.next = null;
                q = temp;
            }
        }
        return dummy.next;
    }
}
